\chapter{Вопрос № 16}

Комбинаторный смысл композиции обыкновенных производящих функций. Примеры.

\section{Вводные определения}

Пусть у нас имеется опф:
\[
	f\left(x\right) = a_1x + a_2x^2 + a_3x^3 + ...
\]
, тогда функция
\[
	F\left(x\right) = \frac{1}{1-f\left(x\right)} = \sum_{n=0}^\infty h_n x^n
\]
является корректно определенной опф, и имеет следующий комбинаторный смысл: пусть у нас имеется линейно упорядоченное множество из $n$ элементов, и пусть $a_n$ количество способов совершить над ними какое-то действие, положим также, что $a_0 = 0$. Тогда $h_n$ - число способов разбить некоторое $n$-множество на какое-то (заранее не определенное) число $k$ блоков, и над каждым блоком размера $i$ совершить комбинаторное действие $a_i$ числом способов.

\section{Примеры}

На плацу стоят в линию $n$ солдат. Дежурный офицер разбивает этот строй на произвольное число $k$ непустых отрядов, а затем в каждом отряде назначает командира. Необходимо посчитать число способов, которым он может это сделать.

В данном случае комбинаторным действием над блоком разделения является выбор командира, тогда очевидно $$ a_n = n $$, а производящая функция описывающая такую последовательность:
\[
	f\left(x\right) = \sum_{i=0}^\infty a_i x^i = \sum_{i=0}^\infty ix^i = \frac{x}{\left(1-x\right)^2}
\]
отсюда получаем производящую функцию для результата:
\[
	\begin{split}
		&F\left(x\right) = \frac{1}{1-f\left(x\right)} = \frac{1}{1 - \frac{x}{\left(1-x\right)^2}} = \\
		& = \frac{1-2x+x^2}{1-3x+x^2} = 1 + \frac{x}{1-3x+x^2}
	\end{split}
\]
теперь разложим в произведение:
\[
	\begin{split}
		&1-3x+x^2 = \left(1-\alpha x\right)\left(1-\beta x\right) = 1 - \left(\alpha+\beta\right)x + \alpha \beta x^2\\
		& \Rightarrow \alpha = \frac{3+\sqrt{5}}{2}; \beta = \frac{3-\sqrt{5}}{2}
	\end{split}
\]
раскладываем на простейщие:
\[
	\frac{1}{1-3x+x^2} = \frac{A}{1-\alpha x} + \frac{B}{1 - \beta x} = \frac{\alpha / \sqrt{5}}{1-\alpha x} - \frac{\beta / \sqrt{5}}{1 - \beta x}
\]
в результате получаем:
\[
	F\left(x\right) = 1 + \frac{x}{\sqrt{5}} \left(\frac{\alpha}{1-\alpha x} - \frac{\beta}{1-\beta x}\right)
\]

\section{Обобщение}

Не обязательно рассматривать композицию опф $\frac{1}{1-x}$ и $f\left(x\right)$, в качестве разбивающей функции можно выбрать и другую опф, например:
\[
	g\left(x\right) = b_0 + b_1 x + b_2 x^2 + ...
\]
Тогда результат композиции:
\[
	h\left(x\right) = \sum_{n=0}^\infty h_n x^n = g\left(f\left(x\right)\right)
\]
можно интерпритировать следующим образом: $h_n$ - число способов разбить $n$- множество на блоки, и над каждым $i$-элементным блоком совершить некоторой действие $a_i$ способами, после чего, над $j$-множеством этих блоков совершить некоторое действие $b_j$ количеством способов.

Опять рассмотрим пример со строем солдат, но теперь мы не выбираем командира в блоке, а выбираем несколько блоков и отправляем их на дежурство. В этом случае производящая функция $$ f\left(x\right) = x + x^2 + x^3 + ... = \frac{x}{1-x} $$. А вот выбрать несколько отрядов из $n$ можно уже $b_n = 2^n$ способами, таким образом имеем производящую функцию:
\[
	g\left(x\right) = 1 + 2x + \left(2x\right)^2 + ... = \frac{1}{1-2x}
\]
композиция определяется следующим образом:
\[
	\begin{split}
		& h\left(x\right) = g\left(f\left(x\right)\right) = \frac{1}{1 - 2\frac{x}{1-x}} = 1 + \frac{2x}{1-3x}\\
		& h_0 = 1\\
		& h_n = 2\cdot3^{n-1}
	\end{split}
\]
